package com.zrf.base.knowledge.leetcode.editor.cn;

/**
 * //给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * //
 * // 示例 1：
 * //
 * // 输入: "babad"
 * //输出: "bab"
 * //注意: "aba" 也是一个有效答案。
 * //
 * //
 * // 示例 2：
 * //
 * // 输入: "cbbd"
 * //输出: "bb"
 * //
 * // Related Topics 字符串 动态规划
 * // 👍 2824 👎 0
 *
 * @author zhouruifeng
 * @date 2020-10-22 07:38:19
 */
public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        System.out.println(solution.longestPalindrome("aba"));
        System.out.println(solution.longestPalindrome("aa"));
        System.out.println(solution.longestPalindrome("aaaa"));
        System.out.println(solution.longestPalindrome("aabac"));
        System.out.println(solution.longestPalindrome("abaaaa"));
    }

    class Solution {
        public String longestPalindrome(String s) {
            if (s == null) {
                return "";
            }
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            String ans = "";

            for (int l = 0; l < n; ++l) {
                for (int i = 0; i + l < n; ++i) {
                    int j = i + l;
                    if (l == 0) {
                        dp[i][j] = true;
                    } else if (l == 1) {
                        dp[i][j] = s.charAt(i) == s.charAt(j);
                    } else {
                        dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                    }

                    if (dp[i][j] && l + 1 > ans.length()) {
                        ans = s.substring(i, i + l + 1);
                    }

                }
            }
            return ans;
        }
    }

}